package com.bigshen.algorithm.aLinearList.solution03CopyListwithRandomPointer;

public class Solution2 {

    public Node copyRandomList(Node head) {

        if (null == head) {
            return head;
        }

        // 1 -> 2 -> 3 -> 4   ==>  1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'
        copy(head);
        copyRandom(head);
        return split(head);
    }

    private void copy(Node head) {
        Node tmp = head;
        while(null != tmp) {
            Node next = tmp.next;
            Node clone = new Node(tmp.val);
            tmp.next = clone;
            clone.next = next;
            tmp = next;
        }
    }

    private void copyRandom(Node head) {
        Node tmp = head;
        while(null != tmp && null != tmp.next) {
            Node next = tmp.next.next;
            if (null != tmp.random) {
                tmp.next.random = tmp.random.next;
            }
            tmp = next;
        }
    }

    // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'  ==>  1 -> 2 -> 3 -> 4
    private Node split(Node head) {
        Node cloneHead = head.next;
        Node pre = head;
        Node current = head.next;
        while(null != pre && null!= current) {
            Node next = current.next;
            pre.next = next;
            if (null != next) {
                current.next = next.next;
            }
            pre = next;
            if (null != next) {
                current = next.next;
            }
        }
        return cloneHead;
    }

}
